Automated Meter Reading (AMR) is part of the Advanced Meter Infrastructure (AMI) that is currently being deployed by Utility Companies. It is network-based, and is a more efficient and accurate method for utility metering data collection, compared to manual on-site meter-reading of electric, gas and water meters.
Various technologies are implemented in AMR/AMI. All implementations perform the tasks of interfacing with the meter to sense consumption, retrieving and communicating back the stored consumption data in the meter to a central site, and storing consumption data in a computer system at the central site. Wireless technologies are getting increasing acceptance in AMR/AMI networks.
Wireless implementations of AMR/AMI are differentiated by being either mobile data collection systems or fixed-wireless data collection networks. Fixed networks may be wireless or wireline. However, the real advantages are with systems based on fixed wireless networks. The distinctive advantages of fixed networks are brought about by the frequent (typically at least daily) consumption data collection, in comparison with mobile AMR systems, which deploy a radio equipped mobile van to drive around the neighborhoods periodically (once a month, for example) to collect meter data over short-range radios for billing purposes. Worth noting among these advantages are: flexibility of billing date; marketing tools such as time-of-use (TOU) rates, demand analysis and load profiling. These enable clearer market segmentation and more accurate forecasts for utility resource generation, and also serve the goal of energy conservation and efficient consumption. Additionally, the utilities benefit from maintenance tools such as outage management and immediate notification of utility resource leakage or account delinquency.
Several methods and systems for implementing fixed network data collection from a plurality of remote devices, such as utility meters, to a central location have been developed and introduced in the past years.
In a typical AMR/AMI network, the utility devices are fully electronic with data reading, data storing, and digital packet communications capabilities. The devices are all linked together in a wireless LAN configuration. In this configuration, each device is a network node. Each node can communicate with other nodes directly and with the Network Management System (NMS) server via relays and Gateways. Typically each node can communicate with more than one Gateway. In networks such as those offering AMR/AMI services, the Gateway acts as an “agent” for the nodes in the wireless network, and transfers the messages between itself, other nodes and the NMS. Similarly, NMS is typically located in an external wide area network (WAN) which may be the Internet or a commercial WAN. The NMS communicates with the nodes in the wireless LAN via the Gateways. Gateways can be passive bridges or active data routers/forwarders, depending on the type of network devices deployed and the applications.
Communications among the NMS, gateways and the nodes of an AMI/AMR network are packet-based, and generally utilize TCP/IP protocols. In some applications, non-TCP/IP protocols are used in the wireless network, and the gateway provides the protocol conversion to TCP/IP. Considerable prior art exists regarding routing of packets, packet architecture, security, etc., that are relevant to computer-based terrestrial and wireless LANs that connect many intelligent remote nodes. The networking technology of Silver Spring Networks is unique in the sense that it is based on a pure IPv6 end-to-end packet architecture, carried by a Layer-2 based wireless LAN routing algorithm.
In wireless network applications where there are a very large number of fixed nodes, the per-node link cost needs to be minimized, and a high bandwidth utilization factor (efficiency) needs to be realized. Utility meter reading and control is characterized by frequent and reliable low-data-rate communication involving a network of a very large number of densely packed nodes.
The innovation presented herein and its predecessor innovations (Dresselhuys, 1997, ref. 5; Nap, 2001, ref. 6; Ehrke, 2003, ref. 7; Ehrke, 2006, ref. 8; Kiiskila, 2007, ref. 9), practiced by Silver Spring Networks, are unique and more efficient than other competing solutions in meeting the requirements of AMR/AMI.
There are many different network and data-link protocols used by ad hoc wireless LANs that are part of utility services networks (AMR, AMI, Smart-Grid, Demand Management, and others). Some of the early ones were developed for use with DSSS-based (Direct-Sequence Spread Spectrum) wireless networks (Dressethuys, 1997, ref. 5; Nap, 2001, ref. 6). The networking described in this Disclosure supports the transfer of commodity utilization data over a two-way spread spectrum wireless local area network to a gateway node connected to a two-way fixed wide area network or connected directly to the utility over a commercially available two-way data communications network (wireline or wireless). An optimized, hop-by-hop, packet routing algorithm is disclosed in these inventions (Dressethuys, 1997, ref. 5; Nap, 2001, ref. 6). The disclosed packet-routing algorithm has evolved (Ehrke, 2006, ref. 8; Kiiskila, 2007 ref. 9), to not require extensive route rediscoveries and routing tables, and it is based on an intelligent next-hop routing scheme. It has worked well in both DSSS and FHSS wireless networks. The algorithm is distinctly different from source routing techniques which take a fundamentally different approach in making packet routing decisions.
Technology and methods for routing of packets in the wireless networks and the Internet have been in constant state of evolution since the days of DARPA packet radio project (Kahn, 1978, ref. 1a). Several packet transmission data formats were evaluated and tested under the DARPA project (Kahn, 1977, ref. 1b), and they became the foundation for the Internet packet routing protocols. Some of the issues surrounding routing information management, etc., as a follow-on of the DARPA project are also well documented (Wescott, 1982, ref. 2; Jubin, 1987, ref. 3). With the advent of the Internet and TCP/IP packet protocols, considerable research has taken place in the areas of terrestrial, fixed wireless, and mobile wireless LANs (Lauer, 1995, ref. 4).
Many routing algorithms, as discussed later, are based on source-routing technique, where the node initiating the packet will provide a route to the destination for the packets to traverse, utilizing the best routing information from its memory. The route is computed regularly and distributed to all nodes by a central node. Local node discoveries are regularly done at the expense of vast network resources to keep routing data current. These techniques are fundamentally different from the dynamic techniques embodied by the invention disclosed here and in its predecessor patents.
There have been some improvements over the basic source routing technique. One of them is the Dynamic Source Routing Protocol (DSR). The initial design of the DSR, including route discovery and route maintenance mechanisms, was first published in December 1994 (Johnson, 1994, ref. 11; Johnson, 1996, ref. 12). The design for routing of IP packets in ad hoc wireless networks based on DSR was submitted to IETFs Mobile Ad Hoc Networks Working Group (MANET) (Broch, 1999, ref. 13).
Initial motivation for the design of DSR came from the operation of the Address Resolution Protocol (ARP), used in the TCP/IP suite of protocols. ARP is used on Ethernet and other broadcast-capable media types of networks to find the link-layer MAC address of a node on the same subnet as the sender.
DSR is similar in approach to the source routing discovery mechanism used in IEEE 802 SRT bridge standard (Perlman, 1992, ref. 14). Related techniques have also been used in other systems including FLIP (Kaashoek, 1993, ref. 15a) and Source Demand Routing Protocol (SDRP) (Estrin, 1995, ref. 16). FLIP grew out of much earlier work on the Amoeba Distributed Operating System (Kaashoek, 1991, ref. 15b). FLIP has the same familiar disadvantages of limited scalability, high costs for broadcast, and the need to maintain extensive routing tables.
DSR allows nodes to discover and maintain source routes to arbitrary destinations in the ad-hoc network. Source routing can work without the need for up-to-date routing in the intermediate nodes through which the packets are forwarded, and it allows nodes forwarding or overhearing packets to cache the routing information in them for their own future use. DSR can operate on demand and scale automatically. However, DSR suffers from endless loops of rediscovery, route maintenance, unexpected link blockages, and other issues. DSR may be more suitable for mobile wireless nodes than for fixed wireless nodes with a limited number of variables; the present invention relates to fixed wireless nodes.
There are other protocols that have used techniques similar to the ones used in DSR. For example, the Signal Stability-based Adaptive Routing Protocol (SSARP) (Dube, 1997, ref. 17) and the Associativity Based Routing Protocol (ABR) (Toh, 1996, ref. 18) each discover routes on demand in a way similar to Route Discovery in DSR, but each attempts to select only long-lived links. ABR also adds overhead for the periodic beacon packets required to monitor link stability. The invention discussed here is distinctly different from the family of source routing protocols including DSR, SSARP, ABR and others, since it is dynamic with no need to maintain extensive routing tables or updates and it does not suffer from repeated route discovery loops.
Other routing protocols have evolved from the early days of packet networks. The Link State Protocol (and various versions of it) and the Distance Vector Protocol (DVP) are two major classes of routing protocols. The Disclosure of this invention and its predecessor patents have some features similar to DVP, but they include additional unique features.
The Link-State Protocol is performed by every node in the network. The basic concept of link-state routing is that every node receives a map of the connectivity of the network. Each node then independently calculates the best next hop from it for routing its packets by using only its local copy of the map and without communicating in any other way with any other node.
The OLSR (Optimized Link State Routing) Protocol (Clausen, 2003, ref. 19) uses the Multi-Point Relay (MPR) technique to reduce the flooding overhead with HELLO messages. The HELLO messages contain all of the adjacent node information, and are used to detect other nodes. The size and number of HELLO messages can increase in densely populated environments, thus causing significant bandwidth overhead and latency. Later improvements of OLSR introduced a compression technique for HELLO messages (“Differential Hello”) (Asami, 2005, ref. 20), wherein redundancies in acknowledgements and information forecasts are eliminated. But there is no clear metric for link cost in this algorithm. Hence the current invention differs from OLSR by specifying clear link cost metrics and by reducing the overhead associated with HELLO messages.
Destination-Sequenced Distance Vector (DSDV) Protocol (Perkins, 1994, ref. 21) is a hop-by-hop destination path protocol. Each network node maintains a routing table that contains the next hop to any reachable destination as welt as the number of hops that will be required. Sequenced updates of routing tables are maintained at each node. But this algorithm as described by Perkins (ref. 21) suffers from a lack of metrics for the actual dynamic “link cost”, heavy bandwidth requirements for route updates, and inflexible routing architecture. This deficiency is eliminated in the modified DSDV version that is the basis of the invention presented herein.
Ad Hoc On-Demand Distance Vector Routing Protocol (AODV) (Perkins, 1999, ref. 22) is a reactive protocol. This means that a node requests a route solely when it needs one and does not require that the nodes maintain destination-based routing information. It is implemented strictly as a Layer-3 protocol. AODV also suffers from scalability problems stemming from its high bandwidth utilization for full-scale on-demand route discovery. The invention discussed here differs from AODV by using a Layer-2 protocol, and by providing an efficient mechanism for route updates.
The Zone Routing Protocol (ZRP) (Haas, 1997, ref. 23) defines a routing zone around each individual node, with a periodic (proactive) protocol such as distance vector or link state for routing within a zone, and an on-demand protocol such as DSR for routing between zones. This technique increases processing overhead and latency. ZRP is a derivative of the “Friends” protocol used by amateur radio operators in the mid-80s, wherein the packet was source-routed to the vicinity (“Zone”), and all nodes within the Zone were required to have the knowledge and capability for terminal delivery of the packet. The invention discussed here is far more sophisticated than ZRP and related techniques since it requires far fewer network and memory resources and it is reliable.
The Location-Aided routing (LAR) (Ko, 1998, ref. 24) proposes an optimization to Route Discovery that uses the GPS-based location information to narrow the area of the network over which the Route Request packets must be propagated. Other techniques use only logical (topological) information (Castaneda, 1999, ref. 25).
Packet radio networks (Takagi et al., 1984, ref. 26) and Metricom's UtiliNet and Ricochet systems (Flammer, 1992, 1995, ref. 27) are examples of relay networks. But the underlying techniques used in UtiliNet and Ricochet are based on a geographic nodal position model where requirements of network connectivity are maintained at each active node. There are several techniques discussed in the Metricom approach about how a new node acquires packet routing information from its neighboring established nodes. A star network routing strategy that guarantees the throughput and forward progress is a strategy known as “nearest neighbor with forward progress (NFP)” (Chou, 1995, ref. 28). But these techniques are still lacking in a robust routing scheme with less overhead and operational loops, as identified in routing techniques that utilize DVRP (Distance vector Routing protocol). These deficiencies are addressed by the current invention.
Some solutions, including Ricochet, call for a complete network topology directory at each node. Resource-intensive solutions such as these are typically too expensive or too complex for applications such as the utility network applications (AMR, AMI, Smart-Grid, etc.). Relay-star routing is also implemented in multi-hop wireless networks (Ore, 1962, ref. 29). This has the property that the graph of the nodes, which are able to communicate directly (in both directions), is a rooted tree. The concentrator is the root of the network tree, and any two nodes are connected by a unique path. Protocols have been developed for relay-star wireless network nodes communicating on a single frequency (FDMA or TDMA). A wireless communications protocol which does not require nodal directories and works in a “relay star” configuration has also been in use. (Guthery, 1997, ref. 10). However, typical relay star routing techniques are prone to packet losses due to limited intelligence in the routing tree. The current invention does not suffer from this deficiency.
There have been other utility network routing techniques discussed for ad-hoc wireless network applications. One such technique, referred to herein as “Brownrigg and Wilson”, (Brownrigg, 2000, 2001, ref. 30) claims to be an improvement over an earlier version utilized in the Metricom Ricochet Network Design. It inaccurately claims that a given radio modem (node) in the Ricochet technique will be in radio contact with only one transceiver of the network. The Brownrigg and Wilson technique claims to minimize the number of hops from the clients to the servers based on the theory that the fewer the number of hops, the better the performance of the network. This is not the case on many occasions in densely packed wireless networks with varying link conditions. There is no quality metric given by Brownrigg and Wilson for calculating the link cost.
The technique utilized in Brownrigg and Wilson is a source routing technique with underlying key features of the OSPF (Open Shortest Path First) Internet routing algorithm. It is distinctly different from routing protocols, such as the invention discussed here, which have Distance Vector Routing Protocol (DVRP) as the basis. Further, Brownrigg and Wilson is dependent on maintaining client link state across multiple nodes which is not a feature of DVRP-based techniques. Further, Brownrigg and Wilson specifies no metric for link cost other than path availability. It utilizes some improvements innovated by Metricom (Baran, 1992; Flammer, 1992; ref. 31) without noting the history of those innovations. In fact, Brownrigg and Wilson may not differ from the entire class of dynamic source routing techniques of Johnson and others described above; it uses very similar techniques.
The protocol described in this innovation, and its predecessor patents which are practiced by Silver Spring Networks, differ significantly from other routing protocols significantly in several areas. For example:                Packet forwarding in Brownrigg and Wilson is source-routed, whereas the innovation reported herein and its predecessor patents use hop by hop forwarding with pre-assessed link cost.        Brownrigg and Wilson uses hop count as the sole metric. The innovation reported herein and its predecessor patents use a combination of hop count, link quality, and latency in route advertisement metrics.        Brownrigg and Wilson assumes that all “internet servers” are the same, assuming they all have the same internet connectivity and there is no reason to prefer one server over another. The innovation reported herein and its predecessor patents allow the end point to discriminate between egress points and related Internet servers. Thus the current invention has intrinsic multi-homing capability        In the innovation reported herein and its predecessor patents, routing decisions are based on best route to the target network not just on the closest egress point.        Brownrigg and Wilson depends on client link state (similar to OSPF), whereas the innovation reported herein and its predecessor patents use a variation of the Distance Vector Routing technique.        The innovation reported herein and its predecessor patents allow one to maintain and use multiple MAC addresses for the nodes within the network, providing capability for IPv6-based multicasting, any casting, and other features of IPv6.        
There are other, less efficient techniques (Bush, 2000, ref. 32) used in utility networks, wherein a regional central station can access any node (monitor) in the network via a unique address and retrieve utility meter data. In this technique, the path from the central station to the destination node is multi-hop in both directions, and the path is sequentially updated or changed by the central station until it receives the response from the node. It is based on star architecture, and utilizes time-consuming response-based techniques. It is a form of the source routing star network solution. The current invention is distinctly different and far superior in performance for wireless utility network applications.
Another reference, Petite, describes a system for relaying data packets in a wireless network between remote devices (effectively, utility meters) and a monitoring network or system through a gateway. (Petite, 2006, ref. 33) A data message including a unique identifier is sent from the remote device, the data message including a unique identifier of the meter and sensor information on the product being metered. The network relays this data message until one remote device forwards the data message to a site controller or gateway. The site controller or gateway uses the unique identifier to send a message to a host computer over a WAN, the message including the meter and sensor information on the product being metered. This system is similar to prior systems from a host of other products practiced by the industry (CellNet, Whisper communications, SSN and others) for many years since 1995, including the technology and products of Silver Spring networks. These products have employed a host of similar techniques since 1994 to relay data messages having a unique identifier for the meter and information on the product that was metered. Further, these systems differ substantially from the routing and network protocols described in the current disclosure and its predecessor patents, and as implemented by Silver Spring Networks. The invention disclosed herein and its predecessor patents, and as implemented by Silver Spring Networks, are unique in the sense they practice IPv6 end-to-end packet architecture, and Layer-2 based hop-by-hop intelligent routing protocol.
Many of the known network routing techniques are some form of centrally computed, tree-based, source-routing distribution schemes. As such, they consume considerable network resources. In the invention presented herein, which is practiced by Silver Spring Networks, the routing protocol is designed to function efficiently in a severely bandwidth- and node memory-constrained environment. Additionally, it is the only end-to-end IPv6 system implementation in AMR/AMI.
The references discussed above are given below:    1. (a) Kahn, Robert E. et al., “Advances in Packet Radio Technology”, Proceedings of the IEEE, vol 66, No 11, pp 1468-1496, November 1978; (b) Kahn, Robert E., “The Organization of Computer Resources in a Packet Radio Network”, Proceedings of the IEEE, vol. Com-25, No. 1, pp. 169-178, January 1977    2. Wescott, J., “Issues in Distributed Routing for Mobile Packet Radio Networks”, Proceedings of the IEEE Global Telecommunications Conference, 1982 (New York: IEEE Press, 1982, pp 233-238).    3. Jubin, John and Tornow, Janet, D., “The DARPA Packet Radio Network Protocols”, Proceedings of the IEEE, vol 75, No 1, pp 21-32, January 1987.    4. Lauer, Gregory S., “Packet-Radio Routing” in Routing in Communications Networks, edited by Martha E. Steenstrup, chapter 11, pp 351-396, Prentice-Hall, Englewood Cliffs, N.J., 1995    5. Dresselhuys, Donn. R, et al., “Meter for Measuring Volumetric Consumption of a Commodity”, U.S. Pat. No. 5,659,300, Innovatec (Silver Spring Networks), Aug. 19, 1997.    6. Nap, Kimbel A. et al., “Automatic Meter Reading Data Communication System”, U.S. Pat. No. 6,246,677, Innovatec (Silver Spring Networks), Jun. 12, 2001.    7. Ehrke, Lance A., et al., “Electronic Electric Meter for Networked Meter Reading”, U.S. Pat. No. 6,538,577, Silver Spring Networks, Mar. 25, 2003.    8. Ehrke, Lance A., et al., “Electronic Electric Meter for Networked Meter Reading”, U.S. Pat. No. 7,064,679, Silver Spring Networks, Jun. 20, 2006.    9. Kiiskila, Marko, et al., “Method and System for Providing a network Protocol for Utility Services”, U.S. Patent Application # 500180978A, Nov. 16, 2006.    10. Guthery, Scott., “Wireless Relay Networks”, IEEE Network Magazine, pp 46-51, November 1997    11. Johnson, David B., “Routing in Ad-Hoc Networks of Mobile Hosts”, Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, IEEE Computer Society, pp 158-163, December 1994.    12. Johnson, David B. and Maltz, David A.: (a) “Dynamic Source Routing in Ad-Hoc Wireless Networks”, in Mobile Computing, edited by Tomasz Imielinski and Hank Korth, chapter 5, pp 153-181, Kluwer Academic Publishers, 1996; (b) “Protocols for Adaptive Wireless and Mobile Networking”, IEEE Personal Communications, vol 3, No. 1, pp 34-42, February 1996.    13. Broch, Josh, Johnson, David B., Maltz, David B., “The Dynamic Source Routing Protocol for Mobile Ad-Hoc Networks”, Draft-IETF-Manet-DSR-03.txt, October 1999.    14. Perlman, Radia., “Interconnections: Bridges and Routers”, Addison-Wesley, Reading, Mass., 1992    15. Kaashoek, Frans M., (a) “FLIP: An Internet Protocol for Supporting Distributed Systems”, ACM Transactions on Computer Systems, vol 11, No. 1, pp 73-106, February 1993; (b) Kaashoek, Frans M.  Tanenbaum, A. S., “Group Communication in the Amoeba Distributed Operating System”, Proceedings of the 11th International Conference on Distributed Computing Systems, pp 222-230, May 1991.    16. Estrin, Deborah, “Source Demand Routing: Packet Format and Forwarding Specification (version 1)”, Internet Draft, January 1995.    17. Dube, Rohit, “Signal Stability-Based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks”, IEEE Personal Communications, vol 4, No 1, pp 36-45, February 1997.    18. Toh, C.-K., “A Novel Distributed Routing Protocol to Support Ad-Hoc Mobile Computing”, Proceedings of the Fifteenth Annual International Phoenix Conference on Computers and Communications, pp 480-486, March 1996.    19. Clausen, T. and Jacquet, P., “Optimized Link State Routing Protocol”, Project Hipercom INRIA Rocquencourt, IETF text, May 2003.    20. Asami, Shigeyuki., et al., “Differential HELLO Technique for Multihop Wireless Network Routing Protocols in Dense Environments”, IEEE Trans. Commun., vol. E88-B, No. 1, January 2005.    21. Perkins, Charles E., and Bhagwat, Pravin., “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, Proceedings of the SIG-COM '94 Conference on Communications Architecture, protocols and Applications, pp 234-244, August 1994.    22. Perkins, Charles E., “Ad-Hoc On-Demand Distance Vector Routing”, Proceedings of the second IEEE Workshop on Mobile Computing Systems and Applications, IEEE Computer Society, pp 90-100, February 1999.    23. Haas, Zygmunt J., “A New Routing Protocol for the Reconfigurable Wireless Networks”, Proceedings of the 6th International Conference on Personal Communications, IEEE pp 562-566, October 1997.    24. Ko, Young-Bae., “Location-Aided Routing (LAR) in Mobile Ad-Hoc Networks”, Proceedings of the 4th International conference on Mobile Computing and Networking, ACM, pp 66-75, October 1998.    25. Castaneda, Robert. And Das, Samir R., “Query Location Techniques for On-Demand Routing Protocols in Ad-Hoc Networks”, Proceedings of the 5th International Conference on Mobile Computing and Networking, ACM, August 1999    26. Takagi et al., “Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals”, IEEE Trans. Commun., vol. Com-32, No 4, pp 246-257, March 1984    27. Flammer, G. H. et al., (a) “Method for Routing Packets in a Packet Communication Network”, U.S. Pat. No. 5,115,433, May 19, 1992; (b) “Method for Network Configuration via Third Party Query”, U.S. Pat. No. 5,453,977, Sep. 26, 1995.    28. Chou, T. C. and Li. V. O. K., “Performance Analysis of Routing Strategies in a Multi-hop Packet Radio Network”, Proc. GLOBECOM '84, Atlanta, Ga., vol 1, pp 487-492, Nov. 26, 1994.    29. Ore, O., “Theory of Graphs”, American Mathematical Society, 1962    30. Brownrigg, Edwin B. and Wilson, Thomas, W., (a) “Wireless Network System and Method for Providing Same”, U.S. Pat. No. 6,044,062, Mar. 28, 2000; (b) “Wireless Network Gateway and Method for Providing Same”, U.S. Pat. No. 6,249,516, Jun. 19, 2001    31. (a) Baran, Paul. et al., “Method and System for Routing Packets in a Packet Communication Network”, U.S. Pat. No. 5,115,433, May 19, 1992; (b) Flammer, George H., et al., “Method for Synchronizing a wide area network without global synchronizing”, U.S. Pat. No. 5,130,987, Jul. 14, 1992    32. Bush, William E., “Demand Reporting of Electricity Consumption by Radio in Relays to a Base Station, and Demand Relays Wattmeters so reporting over a Wide Area”, U.S. Pat. No. 6,078,785, Jun. 20, 2000    33. Petite, Thomas D., “Wireless Communication Networks for Providing Remote Monitoring of Devices”, U.S. Pat. No. 7,103,511, Sep. 5, 2006